#include <stdio.h>
#include <stdlib.h>

#define TEST_SIZE 512


struct queue_elem
{
	int data;
	struct queue_elem *next, *prev;
};

struct queue
{
	struct queue_elem  *first, *last;
	int size;
};

void initQueue( struct queue *p)
{
	p->size = 0;
}


int addElem( struct queue *p, int elem)
{	
	struct queue_elem *new  = malloc( sizeof( struct queue_elem) );
	if ( new == NULL)
	{
		return 0;
	}
	if ( p->size == 0)
	{
		new->data = elem;
		p->last        = p->first = new;
		p->last ->next = p->last ->prev = NULL;
		p->first->next = p->first->prev = NULL;
		
		p->size++;
		return 1;
	}
	p->size++;
	
	new->data = elem;

	new->next = NULL;

	new->prev = p->last;

	p->last->next = new;

	p->last = new;
	
	return 1;
}
int getElem( struct queue *p, int *elem)
{	
	if ( p->size == 0)
	{
		return 0;
	}
	
	if ( p->size == 1)
	{
		*elem = p->first->data;
		p->size--;
		
		free(p->first);
		p->first = NULL;
		p->last  = NULL;
		
		return 1;
	}
	
	p->size--;
	
	
	struct queue_elem *p_tmp = p->first;
	
	*elem = p->first->data;
	
	p->first = p->first->next;
	p->first->prev = NULL;
	
	
	
	free( p_tmp);
	return 1;
}


void delQueue( struct queue *p)
{
	int tmp;
	while ( getElem(p,&tmp));
}


int main( int argc, char** argv)
{
	struct queue A;
	initQueue( &A);
	
	int tmp;
	
	int i;
	for ( i = 1; i < TEST_SIZE ; i++)
	{
		if ( !addElem( &A , i))
		{
			printf("Queue is full");
		}
	}
	
	for ( i = 1; i < TEST_SIZE + 2; i++)
	{
		if ( getElem( &A, &tmp))
		{
			if ( i != tmp)
			{
				printf("Elem[ %d] = %d\n, but should be %d",i,tmp,i);
				printf("\n!!!TEST FAILED\n");
				return 0;
			}
		}
		else
		{	
			if ( (A.size == 0) && (A.first == A.last) && ( A.first == NULL)  )
			{
				//printf("Queue is empty\n");
			}
			else
			{
				printf("Queue isn't empy, but getElem have returned false");
				printf("\n!!!TEST FAILED\n");
				return 0;
			}
		}
	}
	
	delQueue( &A);
	if ( (A.size == 0) && (A.first == A.last) && ( A.first == NULL)  )
	{
	}
	else
	{
		printf("Queue isn't empty after delQueue");
		printf("\n!!!TEST FAILED\n");
		return 0;
	}
	
	printf("\n!!!TEST PASSED\n");
	return 0;
}

